#ifndef SORTING_H
#define SORTING_H

#include <vector>
#include <algorithm>

/**
 * Declare of sorting functions.
 * 
 */

/// Heapsort

template <typename Comparable>
void heapsort(std::vector<Comparable> & a);

template <typename Comparable>
void percDown(std::vector<Comparable> & a, int i, int n);

inline int leftChild(int i);


/// Quicksort

template <typename Comparable>
void quicksort(std::vector<Comparable> & a);

template <typename Comparable>
const Comparable & median3(std::vector<Comparable> & a, int left, int right);

template <typename Comparable>
void quicksort(std::vector<Comparable> & a, int left, int right);


/// Insertionsort

template <typename Comparable>
void insertionSort(std::vector<Comparable> & a, int left, int right);



/**
 * Definitions of sorting functions.
 * 
 */

/// Standard heapsort


template <typename Comparable>
void heapsort(std::vector<Comparable> & a)
{
    for(int i = a.size() / 2 - 1; i >= 0; --i) /// buildHeap
	percDown(a,i,a.size());
    for(int j = a.size() - 1; j > 0; --j)
    {
	std::swap(a[0],a[j]);  /// deleteMax
	percDown(a,0,j);
    }
}

/**
 * Internal method for heapsort.
 * i is the index of an item in the heap.
 * Returns the index of the left child.
 */
inline int leftChild(int i)
{
    return 2 * i + 1;
}

/**
 * Internal method for heapsort that is used in deleteMax and buildHeap.
 * i is the position from which to percolate down.
 * n is the logical size of the binary heap.
 */
template <typename Comparable>
void percDown(std::vector<Comparable> & a, int i, int n)
{
    int child;
    Comparable tmp;

    for(tmp = std::move(a[i]); leftChild(i) < n; i = child)
    {
	child = leftChild(i);
	if(child != n-1 && a[child] < a[child+1])
	    ++child;
	if(tmp < a[child])
	    a[i] = std::move(a[child]);
	else
	    break;
    }
    a[i] = std::move(tmp);
}


/// Classic quicksort

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>
const Comparable & median3( std::vector<Comparable> & a, int left, int right )
{
    int center = ( left + right ) / 2;
    
    if( a[ center ] < a[ left ] )
        std::swap( a[ left ], a[ center ] );
    if( a[ right ] < a[ left ] )
        std::swap( a[ left ], a[ right ] );
    if( a[ right ] < a[ center ] )
        std::swap( a[ center ], a[ right ] );

        // Place pivot at position right - 1
    std::swap( a[ center ], a[ right - 1 ] );
    return a[ right - 1 ];
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void quicksort( std::vector<Comparable> & a, int left, int right )
{
    if( left + 10 <= right )
    {
        const Comparable & pivot = median3( a, left, right );

            // Begin partitioning
        int i = left, j = right - 1;
        for( ; ; )
        {
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                std::swap( a[ i ], a[ j ] );
            else
                break;
        }

        std::swap( a[ i ], a[ right - 1 ] );  // Restore pivot

        quicksort( a, left, i - 1 );     // Sort small elements
        quicksort( a, i + 1, right );    // Sort large elements
    }
    else  // Do an insertion sort on the subarray
        insertionSort( a, left, right );
}

/**
 * Quicksort algorithm (driver).
 */
template <typename Comparable>
void quicksort( std::vector<Comparable> & a )
{
    quicksort( a, 0, a.size( ) - 1 );
}

/// Insertionsort

/**
 * Simple insertionsort.
 * 
 */
template <typename Comparable>
void insertionSort(std::vector<Comparable> & a, int left, int right)
{
    if (left > right - 1)  // The length of array to be sorted is not larger than 1.
	return;
    
    for( int p = left + 1; p < right + 1; ++p )
    {
        Comparable tmp = std::move( a[ p ] );

        int j;
        for( j = p; j > 0 && tmp < a[ j - 1 ]; --j )
            a[ j ] = std::move( a[ j - 1 ] );
        a[ j ] = std::move( tmp );
    }
}



#else
#endif
